package tree;

public class PriorityQueue<T extends Comparable<T>> {
    private T[] data;
    private int size;

    public PriorityQueue(int capacity) {
        data = (T[]) new Comparable[capacity + 1];
    }

    private void sink(int k) {
        int index;
        while (2*k<=this.size){
            if (2*k+1<=this.size){
                index = less(2*k,2*k+1)?2*k+1:2*k;
            }else {
                index=2*k;
            }
            if (!less(k,index)){
                break;
            }
            exchange(k,index);
            k=index;
        }
    }
    private void swim(int k ){
        while (k>1){
            if (!less(k,k/2)){
            exchange(k,k/2);
            }
            k/=2;
        }
    }
    public boolean isEmpty() {
        return this.size == 0;
    }

    public int size() {
        return this.size;
    }
    public void insert(T t){
        data[++this.size] = t;
        swim(size);
    }
    public T delMax(){
        if (this.size==0){
            return null;
        }
        if (this.size==1){
            return data[1];
        }
        T t  = data[1];
        exchange(1,this.size);
        sink(1);
        this.size--;
        return t;
    }
    private boolean less(int i, int j) {
        return data[i].compareTo(data[j]) < 0;
    }

    private void exchange( int i, int j) {
        Comparable temp = data[i];
        data[i] = data[j];
        data[j] = (T) temp;
    }
}
